/**
 * @ClassName Offer21
 * @Description 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
 * @Author clockTown
 * @Date 2021/8/24 9:15
 * @Version 1.0
 */
class Offer21 {
}

/**
 * v0 快慢双指针（极端情况下，如全是奇数时比首尾双指针慢）
 */
class Offer21V0 {
    public int[] exchange(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if ((nums[fast] & 1) == 1){
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
        }
        return nums;
    }
}

/**
 * v1 首尾双指针
 */
class Offer21V1 {
    public int[] exchange(int[] nums) {
        int left = 0, right = nums.length-1, temp;
        while(left < right){
            while((nums[left] & 1) == 1 && left<right){
                left++;
            }
            while((nums[right] & 1) == 0 && right>0){
                right--;
            }
            if(left < right){
                temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }
}

